Computing devices in a software-defined network may not have physical connections, but may be virtually linked to one another. Software-defined networking allows networks to be managed through abstraction of lower level functionality. A control plane in a virtual network usually makes decisions about how to route data packets of network traffic from a source virtual machine in the network to a destination virtual machine. A data plane forwards network traffic to selected destinations. In a software-defined network, methods of network virtualization decouple the control plane of a network from the data plane. Therefore, virtual networks typically have address spaces that bear little resemblance to the topology of the underlying physical network which means that traditional techniques for making networks scale do not work for virtual networks. As a result, routing network traffic through large virtual networks can be problematic using conventional network traffic routing models.